YES 3.62
H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:
↳ HASKELL
↳ BR
mainModule Main
| ((rangeSize :: (Char,Char) -> Int) :: (Char,Char) -> Int) |
module Main where
Replaced joker patterns by fresh variables and removed binding patterns.
Binding Reductions:
The bind variable of the following binding Pattern
r@(vv,vw)
is replaced by the following term
(vv,vw)
The bind variable of the following binding Pattern
b@(wu,wv)
is replaced by the following term
(wu,wv)
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
mainModule Main
| ((rangeSize :: (Char,Char) -> Int) :: (Char,Char) -> Int) |
module Main where
Cond Reductions:
The following Function with conditions
rangeSize | (vv,vw) |
| | null (range (vv,vw)) | |
| | otherwise | |
|
is transformed to
rangeSize | (vv,vw) | = rangeSize2 (vv,vw) |
rangeSize0 | vv vw True | = index (vv,vw) vw + 1 |
rangeSize1 | vv vw True | = 0 |
rangeSize1 | vv vw False | = rangeSize0 vv vw otherwise |
rangeSize2 | (vv,vw) | = rangeSize1 vv vw (null (range (vv,vw))) |
The following Function with conditions
is transformed to
undefined0 | True | = undefined |
undefined1 | | = undefined0 False |
The following Function with conditions
takeWhile | p [] | = [] |
takeWhile | p (x : xs) | |
is transformed to
takeWhile | p [] | = takeWhile3 p [] |
takeWhile | p (x : xs) | = takeWhile2 p (x : xs) |
takeWhile1 | p x xs True | = x : takeWhile p xs |
takeWhile1 | p x xs False | = takeWhile0 p x xs otherwise |
takeWhile0 | p x xs True | = [] |
takeWhile2 | p (x : xs) | = takeWhile1 p x xs (p x) |
takeWhile3 | p [] | = [] |
takeWhile3 | xu xv | = takeWhile2 xu xv |
The following Function with conditions
index | (wu,wv) ci |
| | inRange (wu,wv) ci |
= | fromEnum ci - fromEnum wu |
|
| | otherwise | |
|
is transformed to
index | (wu,wv) ci | = index2 (wu,wv) ci |
index1 | wu wv ci True | = fromEnum ci - fromEnum wu |
index1 | wu wv ci False | = index0 wu wv ci otherwise |
index0 | wu wv ci True | = error [] |
index2 | (wu,wv) ci | = index1 wu wv ci (inRange (wu,wv) ci) |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
mainModule Main
| ((rangeSize :: (Char,Char) -> Int) :: (Char,Char) -> Int) |
module Main where
Let/Where Reductions:
The bindings of the following Let/Where expression
fromEnum c <= i && i <= fromEnum c' |
where | |
are unpacked to the following functions on top level
inRangeI | xx | = fromEnum xx |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
mainModule Main
| ((rangeSize :: (Char,Char) -> Int) :: (Char,Char) -> Int) |
module Main where
Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
mainModule Main
| (rangeSize :: (Char,Char) -> Int) |
module Main where
Haskell To QDPs
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_primPlusInt(xy24, Succ(xy250)) → new_primPlusInt(xy24, xy250)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primPlusInt(xy24, Succ(xy250)) → new_primPlusInt(xy24, xy250)
The graph contains the following edges 1 >= 1, 2 > 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_primPlusInt0(Succ(xy440), Succ(xy430)) → new_primPlusInt0(xy440, xy430)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primPlusInt0(Succ(xy440), Succ(xy430)) → new_primPlusInt0(xy440, xy430)
The graph contains the following edges 1 > 1, 2 > 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_primPlusInt1(xy43, xy44, Succ(xy450)) → new_primPlusInt1(xy43, xy44, xy450)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primPlusInt1(xy43, xy44, Succ(xy450)) → new_primPlusInt1(xy43, xy44, xy450)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
new_primPlusInt2(xy35, xy36, Succ(xy370), Succ(xy380)) → new_primPlusInt2(xy35, xy36, xy370, xy380)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primPlusInt2(xy35, xy36, Succ(xy370), Succ(xy380)) → new_primPlusInt2(xy35, xy36, xy370, xy380)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3, 4 > 4
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ LetRed
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
Q DP problem:
The TRS P consists of the following rules:
new_rangeSize1(xy17, xy18, Succ(xy190), Succ(xy200), ba) → new_rangeSize1(xy17, xy18, xy190, xy200, ba)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_rangeSize1(xy17, xy18, Succ(xy190), Succ(xy200), ba) → new_rangeSize1(xy17, xy18, xy190, xy200, ba)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3, 4 > 4, 5 >= 5